1. Field of the Invention
This invention generally relates to real-time systems, in particular it relates to garbage collectors for memory reclamation in systems with hard deadlines.
2. Description of the Related Art
Run-time support systems for most modern programming languages provide a memory management package with which the user can dynamically allocate and deallocate storage for objects. Some memory management packages are automatic in the sense that they reclaim the storage associated with an object when the package can determine that the application can no longer use that object. The component that performs this service is commonly called the garbage collector.
Automatic memory management is a valuable tool for complex applications. It can simplify the task of an application programmer since he can use complex dynamic data structures without having to explicitly determine constituent lifetimes. This freedom can result in more robust applications since subtle errors involving premature or missed deallocation are not possible. Automatic memory management is a fundamental or desirable feature of many programming languages.
Many garbage collectors have been described that are real-time in the sense that they can be guaranteed to reclaim memory faster than the application can allocate it. This macro-level property is not sufficient for a hard real-time system since it is still possible for deadlines to be missed due to micro-level side effects of executing the collector. It is desirable to have a garbage collector that is compatible with hard real-time execution.
A first problem in implementing a real-time garbage collector is providing adequate computational resources to reclaim storage. The time required to reclaim memory is typically much longer than the execution times and deadlines of the hard real-time tasks because reclamation must access a significant fraction of system memory. For the system to be responsive to external events while reclamation is occurring, a procedure may be used for memory reclamation whose execution is interleaved with application tasks.
Another problem is minimizing the impact of the collector on the schedulability of application tasks. Methods for memory reclamation typically involve scanning objects, relocating pointers, and copying objects. These operations cannot be safely interrupted by application tasks that use the automatic memory management abstraction and thus become critical sections during which execution of the application is blocked. It is essential that the duration of such atomic operations be tightly bounded so the reclamation process's interference with the application tasks can be assessed and held to practical values For example, a procedure that must copy an object atomically is undesirable if worst-case behavior must be handled; any task has the potential to be delayed for the time required to copy the largest allocated object.
Another problem is maintaining predictable execution times for application tasks. The choice of reclamation method can affect the execution time of an application task due to the overhead associated with invoking the memory management abstraction. For example, some designs have the property that any access to an object may require that the object be copied from one area of storage to another. It is important to design a procedure that has a uniform and tightly bound overhead so it is possible to automatically or manually determine the execution time of application tasks.
One category of garbage collectors is "copying" collectors. In these, live objects are separated from dead (garbage) objects by copying the live objects to a new area and discarding the dead objects and the original instances of the live objects. This type of collector has the advantage that it compacts the live objects together. However, it has the disadvantage that references to old objects must be adjusted to point to the new copies. Typical implementations use "barriers" on read, write, and object identity tests that occur in application programs. The barriers ensure that consistency is maintained while objects are being transported. Because read operations tend to be more frequent than write and identity tests, it is more efficient to not require a read barrier; accordingly, it is desirable to require the special handling, required by a "barrier," only on write and identity test operations.
Accordingly, improvements which overcome any or all of the problems are presently desirable.